package arithmetic;

import arithmetic2.TreeNode;
import utils.PrintUtil;

import java.util.*;

/**
 * @Author: Jie
 * @Date: 2019/1/21 10:15
 * @Function :
 * BinarySearchTree 存在的意义：搜索插入的凭据复杂程度为log2n 远小于O n
 * <p>
 * leetcode 98 验证二叉搜索树
 * <p>
 * 前序、中序、后序
 * 广度优先？深度优先？
 * <p>
 * 前中后 说明：
 * https://blog.csdn.net/qq_33243189/article/details/80222629
 * 为啥叫这个名字？是根据根节点的顺序命名的。
 * <p>
 * A
 * B     C
 * 前序遍历：ABC   根-》左-》右
 * 中序遍历：BAC   左-》根-》右   遍历出的结果是有序的array
 * 后序遍历：BCA   左-》右-》根
 * <p>
 * 1） 二叉树的深度优先遍历的非递归的通用做法是采用栈???忘记了待查，广度优先遍历的非递归的通用做法是采用队列。
 * <p>
 * 2） 深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历。具体说明如下：
 * <p>
 * 先序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。
 * 中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。
 * 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
 */
public class A_09_BinaryTree {

    public static void main(String[] args) {
        TreeNode treeRoot = getTreeRootNode();
        PrintUtil.print(bfsRowList(treeRoot));

//        时间复杂度：O (n)
        //方法一 判断中序遍历有是否有序
//        boolean isValid = isValidBST(treeRoot);

        //        时间复杂度：O (n)
        //方法二 递归 查询  左子树最大值< 根节点<右子树 最小值
//        boolean isValid2 = isValidBSTRecursion(treeRoot,Long.MIN_VALUE,Long.MAX_VALUE);
//        System.out.println("isValid=="+isValid);


//        ArrayList<Integer> integers = PrintFromTopToBottom(treeRoot);
        List<Integer> mlist = new ArrayList<>();
        //前
//        preOrderTraverse(treeRoot, mlist);
        //中
//        InOrder(treeRoot,mlist);
        //后
        postOrderTraverse(treeRoot,mlist);

        PrintUtil.print(mlist);


        //非递归，dfs
//        iterativePreorder(treeRoot);
//        iterativeInOrder(treeRoot);
        iterativePostOrder(treeRoot);
    }

    /**
     * 5
     * 3      8
     * 1  4   6  10
     */
    public static TreeNode getTreeRootNode() {
        /**
         *      5
         *  3      8
         * 1  4   6  10
         */
        TreeNode treeRoot = new TreeNode(5);
        TreeNode tree3 = new TreeNode(3);
        TreeNode tree1 = new TreeNode(1);
        TreeNode tree4 = new TreeNode(4);

        TreeNode tree8 = new TreeNode(8);
        TreeNode tree6 = new TreeNode(6);
        TreeNode tree10 = new TreeNode(10);
        treeRoot.left = tree3;
        tree3.left = tree1;
        tree3.right = tree4;
        treeRoot.right = tree8;
        tree8.left = tree6;
        tree8.right = tree10;
        return treeRoot;
    }

    //判断是否 是有序二叉树
    //中序遍历，判断是否有序
    private static boolean isValidBST(TreeNode root) {
        List<Integer> mList = new ArrayList<>();

        //把遍历，加入数组。
        InOrder(root, mList);

        //判断是否为升序。
        for (int i = 1; i < mList.size(); i++) {
            System.out.print(",");
            System.out.print(mList.get(i));
            if (mList.get(i - 1) >= mList.get(i)) {
                return false;
            }
        }
        return true;
    }
    //中序 遍历 成为升序。 可以不返回值 临时保存前继节点
    private static void InOrder(TreeNode root, List<Integer> mList) {
        if (root == null) {
            return;
        }
        InOrder(root.left, mList);
        mList.add(root.val);
        InOrder(root.right, mList);
    }

    //判断是否 是有序二叉树
    //递归 左< 中 < 右
    //     *      5
    //     *  3      8
    //     * 1  4   4  10
    //node==5  min:-9223372036854775808  max:9223372036854775807  root.val<=minVal:false   root.val>=maxVal:false
    //node==3  min:-9223372036854775808  max:5  root.val<=minVal:false   root.val>=maxVal:false
    //node==1  min:-9223372036854775808  max:3  root.val<=minVal:false   root.val>=maxVal:false
    //node==4  min:3  max:5  root.val<=minVal:false   root.val>=maxVal:false
    //node==8  min:5  max:9223372036854775807  root.val<=minVal:false   root.val>=maxVal:false
    //node==4  min:5  max:8  root.val<=minVal:true   root.val>=maxVal:false
    public static boolean isValidBSTRecursion(TreeNode root, long minVal, long maxVal) {
        if (root == null) {
            return true;
        }

        System.out.println("node==" + root.val + "  min:" + minVal + "  max:" + maxVal + "  root.val<=minVal:" + (root.val <= minVal) + "   root.val>=maxVal:" + (root.val >= maxVal));
        if (root.val <= minVal || root.val >= maxVal) {//根节点 <= min false, 根节点 >= max false.
            return false;
        }

        return isValidBSTRecursion(root.left, minVal, root.val)//判断左节点，更新最大值。
                && isValidBSTRecursion(root.right, root.val, maxVal);//判断右节点，更新最小值。
    }

    //前序 根-》左-》右
    //结果：start print **************
    //[5],[3, 8],[1, 4, 6, 10],
    //over print **************
    //start print **************
    //5,3,1,4,8,6,10,
    //over print **************
    private static void preOrderTraverse(TreeNode root, List<Integer> mList) {
        if (root == null) {
            return;
        }
        mList.add(root.val);
        preOrderTraverse(root.left, mList);
        preOrderTraverse(root.right, mList);
    }

    //后序 左-》右-》根
    private static void postOrderTraverse(TreeNode root, List<Integer> mList) {
        if (root == null) {
            return;
        }
        postOrderTraverse(root.left, mList);
        postOrderTraverse(root.right, mList);
        mList.add(root.val);
    }

    //广度 优先遍历Breadth FirstSearch
    // 对每一层节点依次访问，访问完一层进入下一层
    // 前序遍历 + 队列
    public static ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> lists = new ArrayList<Integer>();
        if (root == null)
            return lists;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();//临时缓存。
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode tree = queue.poll();//poll即将加入到集合的元素。
            if (tree.left != null)
                queue.offer(tree.left);// 左 ，下一行的。
            if (tree.right != null)
                queue.offer(tree.right);//右 ，下一行的。

            lists.add(tree.val);//加入到集合。
        }
        return lists;
    }

    //bfs 按行打印，
    //广度优先遍历 安行打印， 前序遍历 + 队列 +计数
    private static List<List<Integer>> bfsRowList(TreeNode root) {
        if (root == null) {
            return null;
        }
        List<List<Integer>> mList = new ArrayList<>();//最后的结果
        LinkedList<TreeNode> mQueue = new LinkedList<>();//队列
        mQueue.offer(root);
        int rowNumSize;

        while (!mQueue.isEmpty()) {
            rowNumSize = mQueue.size();//每行的大小
            List<Integer> rowList = new ArrayList<>();//每一行
            for (int i = 0; i < rowNumSize; i++) {//当前行的大小，循环内加入下一行的所有元素。
                TreeNode poll = mQueue.poll();//poll 当前行。
                if (poll.left != null) {
                    mQueue.offer(poll.left);
                }
                if (poll.right != null) {
                    mQueue.offer(poll.right);
                }
                rowList.add(poll.val);//当前行。
            }
            mList.add(rowList);
        }

        return mList;
    }


    // print-访问树的节点
    public static void visit(TreeNode node) {
        System.out.println(node.val);
    }

    /**
     * 非递归,二叉树,先序遍历
     * 入栈顺序： 根 ，右 左
     * 出站顺序： 根 ，左 右
     */
    public static void iterativePreorder(TreeNode node) {
        Stack<TreeNode> stack = new Stack<>();
        if (node != null) {
            stack.push(node);// 根
            while (!stack.empty()) {
                node = stack.pop();// 先访问根节点
                visit(node); //根
                // 把右子结点压入栈
                if (node.right != null) {
                    stack.push(node.right);//右
                }
                // 把左子结点压入栈
                if (node.left != null) {
                    stack.push(node.left);//左
                }
            }
        }
    }

    /**
     * 非递归实现二叉树的中序遍历
     */
    public static void iterativeInOrder(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (node != null || stack.size() > 0) {
            // 把当前节点的所有左侧子结点压入栈
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            // 访问节点，处理该节点的右子树
            if (stack.size() > 0) {
                node = stack.pop();
                visit(node);
                node = node.right;
            }
        }
    }

    /**
     * 后序遍历，非递归，使用单栈实现二叉树
     */
    public static void iterativePostOrder(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        // 访问根节点时判断其右子树是够被访问过
        TreeNode preNode = null;
        while (node != null || stack.size() > 0) {
            // 把当前节点的左侧节点全部入栈
            while (node != null) {
                stack.push(node);//根
                node = node.left;
            }
            if (stack.size() > 0) {
                TreeNode temp = stack.peek().right;//
                // 一个根节点被访问的前提是：无右子树或右子树已被访问过
                if (temp == null || temp == preNode) {
                    node = stack.pop();
                    visit(node);
                    preNode = node;// 记录刚被访问过的节点
                    node = null;
                } else {
                    // 处理右子树
                    node = temp;
                }
            }
        }
    }
}


